<?php
//include_once("class_segment.php");
//include_once("class_unit.php");
//include_once("inc_str.php");
//include_once("inc_array.php");

class Tool_segment_light{

  public static function get_char(&$_str,$_offset){
    return mb_substr($_str,$_offset,1);
  }

  public static function tostring(&$_seg,&$_str){
    return mb_substr($_str,$_seg[0],$_seg[1]);
  }

  public static function tostringpartial(&$_seg,&$_str,$_len){
    return mb_substr($_str,$_seg[0],$_len);
  }
  
  public static function totruesegment(&$_seg,&$_str){
    return new Segment($_str,$_seg[0],$_seg[1]);
  }

  public static function toarrayletter(&$_seg,&$_str,&$_alphabet){
    $res=array();
    for($i=0;$i<$_seg[1];$i++){
      $l=self::get_char($_str,$i+$_seg[0]);
      $_alphabet[$l]=1;
      $res[]=$l;
    }
    return $res;
  }

  public static function toarrayrevletter(&$_seg,&$_str,&$_alphabet){
    $res=array();
    for($i=0;$i<$_seg[1];$i++){
      $l=self::get_char($_str,$_seg[0]+$_seg[1]-$i-1);
      $_alphabet[$l]=1;
      $res[]=$l;
    }
    return $res;
  }

  public static function get_same_prefix(&$_seg1,&$_seg2,&$_str1,&$_str2){
    $len=min($_seg1[1],$_seg2[1]);
    for($i=0;$i<$len && (mb_substr($_str1,$i+$_seg1[0],1)==mb_substr($_str2,$i+$_seg2[0],1));$i++);
    return $i;
  }

  public static function does_include_strict(&$_seg1,&$_seg2){
    //$ostart=$_seg2[0];
    //$offset_end=$offset_start+$_seg2[1];
    //$start=$_seg1[0];
    //$end=$start+$_seg1[1];
    return ($_seg1[0]+$_seg1[1]>=$_seg2[0]+$_seg2[1] and $_seg1[0]<=$_seg2[0]) ? true : false;
  }

//tri par longueur
 public static function usort_len($i,$j){
  if($i[1] < $j[1]) return -1;
  else return ($i[1] > $j[1]) ? 1 : 0;
 }

//tri par position
 public static function usort_offset($i,$j){
  if($i[0] < $j[0]) return -1;
  else return ($i[0] > $j[0]) ? 1 : 0;
 }

}

class suffixarray{
  private $array_str=array();
  private $array_suffix=array();
  private $array_repeated=array();
  private $array_distrib=array();

  private $global_suffix=array();
  private $global_res=array();
  private $global_equiv=array();
  private $alphabet=array();
  private $n=0;

  private $lcp=array();

  public function __construct(){}

  public function __add_str(&$_str){
    $id_str=array_push($this->array_str,$_str)-1;
    $str_len=mb_strlen($_str);
    $mot=array();
    for($i=0;$i<$str_len;++$i){
      $this->array_suffix[]=array($i,$str_len-$i,$id_str);
      $l=mb_substr($_str,$i,1);
      $mot[]=$l;
      $this->alphabet[$l]=1;
    }
    $this->global_equiv[]=$mot;
  }

  public function usort_segment(&$_seg1,&$_seg2){
    return strcmp(
      Tool_segment_light::tostring($_seg1,$this->array_str[$_seg1[2]]),
      Tool_segment_light::tostring($_seg2,$this->array_str[$_seg2[2]])
    );
  }

  public function rstr($b,$e){
    $min=$this->lcp[$b];
    $minpos=array($b);
    $k=1;
    for($i=$b+1;$i<$e;++$i){
      if($min>$this->lcp[$i]){
        $min=$this->lcp[$i];
        $minpos=array($i);
        $k=1;
      }
      elseif($min == $this->lcp[$i]) $minpos[$k++]=$i;
    }
    if($min>0){
      $pos=array();
      for($i=$b;$i<=$e;++$i){
        $su=$this->array_suffix[$i-1];
        $su[1]=$min;
        $pos[]=$su;
      }
      $str=tool_segment_light::tostring($su,$this->array_str[$su[2]]);
      $this->rstr[$str]=$pos;
    }

    if($k != $e-$b){
      $ppos=$b;
      $minpos[$k++]=$e;
      for($i=0;$i<$k;$i++){
        if($minpos[$i]-$ppos>0) $this->rstr($ppos,$minpos[$i]);
        $ppos=$minpos[$i]+1;
      }
    }
  }

  public function sort_suffix(){
   $start=microtime(true);
   $this->alphabet=array_keys($this->alphabet);
   sort($this->alphabet,SORT_STRING);
   $f=chr(ord(reset($this->alphabet))-1);  
   $nf=chr(ord($f)-1);
   array_unshift($this->alphabet,$f);
   $distrib=$res=array();
   $x=0;
   foreach($this->global_equiv as $id_suffix=>$mot){
    foreach($mot as $lettre){
      $cpt=array_push($this->global_suffix,$lettre)-1;
      $distrib[$cpt]=$x++;
      $res[]=0;
      ++$this->n;
//      ++$x;
    }
     $this->global_suffix[]=$f;
     $res[]=0;
     ++$this->n;
   }

   $res[]=$res[]=$res[]=0;
   $this->global_suffix[]=$this->global_suffix[]=$this->global_suffix[]="$nf";
   sortSuffixArray($this->global_suffix,$res,$this->n,$this->alphabet);
   $time=microtime(true)-$start;
   echo "1 : $time\n";

   $rank=$SA=$tmp=array();
   $k=0;
   for($i=0;$i<$this->n;++$i){
    if(isset($distrib[$res[$i]])){
      $rank[$distrib[$res[$i]]]=$k;
      $SA[$k++]=$distrib[$res[$i]];
      $tmp[]=$this->array_suffix[$distrib[$res[$i]]];
//      ++$k;
    }
   } 

   for($j=0;$j<$k;++$j){
     if($l>0)--$l;
     if($rank[$j]!=0){
       $segj=$this->array_suffix[$j];
       $segjj=$this->array_suffix[$SA[$rank[$j]-1]];
       while($l<$segj[1] and $l<$segjj[1] and
             mb_substr($this->array_str[$segj[2]],$l+$segj[0],1)==mb_substr($this->array_str[$segjj[2]],$l+$segjj[0],1)){
              ++$l; 
       }
     }
     else $l=0;
     $this->lcp[$rank[$j]]=$l;
   }
  $this->lcp[$k]=0;
  $this->array_suffix=$tmp;
  $this->rstr(0,$k);

  unset($lcps);
  unset($this->global_suffix);
  unset($this->global_equiv);
  $time=microtime(true)-$start;
  echo '2: ' . number_format(memory_get_usage(), 0, '.', ',') . " bytes\n";
  echo "2 : $time\n";
   die();
  }

  public function __init(){
//    print_r($this);
//    echo '0: ' . number_format(memory_get_usage(), 0, '.', ',') . " bytes\n";
    $start=microtime(true);
//    usort($this->array_suffix,array($this,"usort_segment"));
    $this->sort_suffix();
    $time=microtime(true)-$start;
//    echo "1+2 : $time\n";
//    echo '1+2: ' . number_format(memory_get_usage(), 0, '.', ',') . " bytes\n";
//    die();
//    return;
//    $start=microtime(true);
//    $res=$this->step2();
//    $time=microtime(true)-$start;
//    echo "2 : $time\n";
//die();
    $start=microtime(true);
    $this->step3();
    $time=microtime(true)-$start;
    echo "3 : $time\n";
//    die();
    $start=microtime(true);
    $this->step4();
    $time=microtime(true)-$start;
    echo "4 : $time\n";
    $start=microtime(true);
    $this->step5();
    $time=microtime(true)-$start;
    echo "5 : $time\n";

    return $this->array_distrib;
  }


 private function step2(){
  $lcps=array();
  $len=count($this->array_suffix);
  for($i=0;$i<$len-1;$i++){
   $seg1=$this->array_suffix[$i];
   $seg2=$this->array_suffix[$i+1];
   $lcps[$i]=Tool_segment_light::get_same_prefix($seg1,$seg2,$this->array_str[$seg1[2]],$this->array_str[$seg2[2]]);
  }
  $lcps[$i]=0;
  return $lcps;
 }

 private function step3(){
  $res=$res2=$return=array();
//  $max=count($_lcps);
//  $valid=array();
  $start=microtime(true);
/*
  foreach($this->group_lcps as $i=>$array_lg){
    foreach($array_lg as $lg=>$mt){
       $str=mb_substr($this->array_str[$this->array_suffix[$i][2]],$this->array_suffix[$i][0],$lg);
       $this->array_repeated[$str][]=array($this->array_suffix[$i][0],$lg,$this->array_suffix[$i][2]);      
    }
  }


  ksort($this->array_repeated,SORT_STRING);
  foreach($this->array_repeated as $str=>$array){
    echo "[$str]";
    echo "\n";
  }
die();
*/
  $this->array_repeated=$this->rstr;
  unset($this->group_lcps);
  unset($this->array_suffix);
  $time=microtime(true)-$start;
  echo "3.X0 : $time\n";
//  echo '3.X0: ' . number_format(memory_get_usage(), 0, '.', ',') . " bytes\n";
  $start=microtime(true);
  $tmp=$alphabet=array();
  foreach($this->array_repeated as $str=>$array){
    usort($this->array_repeated[$str],array($this,"step3_usort_new"));
    $tmp[$str]=tool_segment_light::toarrayrevletter($array[0],$this->array_str[$array[0][2]],$alphabet);
  }
  $time=microtime(true)-$start;
//  print_r($this->array_repeated);
//die();
  echo "3.X1 : $time\n";
//  echo '3.X1 : ' . number_format(memory_get_usage(), 0, '.', ',') . " bytes\n";
  $start=microtime(true);
  $alphabet=array_keys($alphabet);
  sort($alphabet,SORT_STRING);
  $first=chr(ord(reset($alphabet))-1);
  $nfirst=chr(ord($first)-1);
  array_unshift($alphabet,$first);
  $mot=$distrib=array();
  foreach($tmp as $str=>$arrayl){
    $flag=true;
    foreach($arrayl as $l){
      $cpt=array_push($mot,$l)-1;
      if($flag){
        $distrib[$cpt]=$str;
        $flag=false;
      }
    }
    $mot[]=$first;
  }
  $n=count($mot);
  $mot[]=$mot[]=$mot[]=$nfirst;
//  $ordered[]=$ordered[]=$ordered[]=0;
  $ordered=array_fill(0,$n+3,0);
//  echo '3.X210: ' . number_format(memory_get_usage(), 0, '.', ',') . " bytes\n";
//  unset($tmp);
  unset($tmp);
  $time=microtime(true)-$start;
//  echo "3.X21 : $time\n";
//  echo '3.X21: ' . number_format(memory_get_usage(), 0, '.', ',') . " bytes\n";
//  echo "$n";
  $start=microtime(true);
  sortSuffixArray($mot,$ordered,$n,$alphabet);
  $time=microtime(true)-$start;
echo "3.X22 : $time\n";
//echo '3.X22: ' . number_format(memory_get_usage(), 0, '.', ',') . " bytes\n";
//  die();

  $start=microtime(true);
  $tmp=array();
  for($i=0;$i<$n;$i++){
    if(isset($distrib[$ordered[$i]]))
      $tmp[]=$this->array_repeated[$distrib[$ordered[$i]]];
  }
  $this->array_repeated=$tmp;
  $time=microtime(true)-$start;
  echo "3.X23 : $time\n";
 }



 private function step3_usort_new($i,$j){
//  if($i[3]<$j[3]) return -1;
//  elseif($i[3]>$j[3])return 1;
  if($i[2]<$j[2]) return -1;
  elseif($i[2]>$j[2]) return 1;
//  elseif($i[1]<$j[1]) return -1;
//  elseif($i[1]>$j[1]) return 1;
  else return $i[0]-$j[0];
}


//tri des suffix
 private function usort_rev($_seg1,$_seg2){
   $lenmin=min($_seg1[1],$_seg2[1]);
   $oi=$_seg1[1]+$_seg1[0]-1;
   $oj=$_seg2[1]+$_seg2[0]-1;
   while($lenmin and
         (Tool_segment_light::get_char($this->array_str[$_seg1[2]],$oi)==Tool_segment_light::get_char($this->array_str[$_seg2[2]],$oj))){
    --$lenmin;--$oi;--$oj;
   }
   if(!$lenmin){return $_seg1[1]-$_seg2[1];}
   else{
     return (Tool_segment_light::get_char($this->array_str[$_seg1[2]],$oi)<Tool_segment_light::get_char($this->array_str[$_seg2[2]],$oj))? -1 : 1;
   }
 }

 private function usort_rev_array($_array_seg1,$_array_seg2){
  return $this->usort_rev($_array_seg1[0],$_array_seg2[0]);
 }

 private function step4(){
  $max=count($this->array_repeated);
  for($i=0;$i<$max-1;$i++){
   if(tool_segment_light::does_include_strict($this->array_repeated[$i+1][0],$this->array_repeated[$i][0])
      and count($this->array_repeated[$i])==count($this->array_repeated[$i+1]))
      unset($this->array_repeated[$i]);
  }
 }

 private function step5(){
  foreach($this->array_repeated as $repeated){
   $str=tool_segment_light::tostring($repeated[0],$this->array_str[$repeated[0][2]]);
   foreach($repeated as $segment){
    $this->array_distrib[$str][]=tool_segment_light::totruesegment($segment,$this->array_str[$segment[2]]);
   }
  }
  ksort($this->array_distrib);
 }


}

?>
